{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #K Highest Ranked Items Within a Price Range"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #breadth-first-search #array #matrix #sorting #heap-priority-queue"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #广度优先搜索 #数组 #矩阵 #排序 #堆（优先队列）"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: highestRankedKItems"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #价格范围内最高排名的 K 样物品"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个下标从 <strong>0</strong>&nbsp;开始的二维整数数组&nbsp;<code>grid</code>&nbsp;，它的大小为&nbsp;<code>m x n</code>&nbsp;，表示一个商店中物品的分布图。数组中的整数含义为：</p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>0</code>&nbsp;表示无法穿越的一堵墙。</li>\n",
    "\t<li><code>1</code>&nbsp;表示可以自由通过的一个空格子。</li>\n",
    "\t<li>所有其他正整数表示该格子内的一样物品的价格。你可以自由经过这些格子。</li>\n",
    "</ul>\n",
    "\n",
    "<p>从一个格子走到上下左右相邻格子花费&nbsp;<code>1</code>&nbsp;步。</p>\n",
    "\n",
    "<p>同时给你一个整数数组&nbsp;<code>pricing</code> 和&nbsp;<code>start</code>&nbsp;，其中&nbsp;<code>pricing = [low, high]</code> 且&nbsp;<code>start = [row, col]</code>&nbsp;，表示你开始位置为&nbsp;<code>(row, col)</code>&nbsp;，同时你只对物品价格在<strong>&nbsp;闭区间</strong>&nbsp;<code>[low, high]</code>&nbsp;之内的物品感兴趣。同时给你一个整数&nbsp;<code>k</code>&nbsp;。</p>\n",
    "\n",
    "<p>你想知道给定范围 <strong>内</strong>&nbsp;且 <strong>排名最高</strong>&nbsp;的 <code>k</code>&nbsp;件物品的 <strong>位置</strong>&nbsp;。排名按照优先级从高到低的以下规则制定：</p>\n",
    "\n",
    "<ol>\n",
    "\t<li>距离：定义为从&nbsp;<code>start</code>&nbsp;到一件物品的最短路径需要的步数（<strong>较近</strong>&nbsp;距离的排名更高）。</li>\n",
    "\t<li>价格：<strong>较低</strong>&nbsp;价格的物品有更高优先级，但只考虑在给定范围之内的价格。</li>\n",
    "\t<li>行坐标：<strong>较小</strong>&nbsp;行坐标的有更高优先级。</li>\n",
    "\t<li>列坐标：<strong>较小</strong>&nbsp;列坐标的有更高优先级。</li>\n",
    "</ol>\n",
    "\n",
    "<p>请你返回给定价格内排名最高的 <code>k</code>&nbsp;件物品的坐标，将它们按照排名排序后返回。如果给定价格内少于 <code>k</code>&nbsp;件物品，那么请将它们的坐标&nbsp;<strong>全部</strong>&nbsp;返回。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/12/16/example1drawio.png\" style=\"width: 200px; height: 151px;\"></p>\n",
    "\n",
    "<pre><b>输入：</b>grid = [[1,2,0,1],[1,3,0,1],[0,2,5,1]], pricing = [2,5], start = [0,0], k = 3\n",
    "<b>输出：</b>[[0,1],[1,1],[2,1]]\n",
    "<b>解释：</b>起点为 (0,0) 。\n",
    "价格范围为 [2,5] ，我们可以选择的物品坐标为 (0,1)，(1,1)，(2,1) 和 (2,2) 。\n",
    "这些物品的排名为：\n",
    "- (0,1) 距离为 1\n",
    "- (1,1) 距离为 2\n",
    "- (2,1) 距离为 3\n",
    "- (2,2) 距离为 4\n",
    "所以，给定价格范围内排名最高的 3 件物品的坐标为 (0,1)，(1,1) 和 (2,1) 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/12/16/example2drawio1.png\" style=\"width: 200px; height: 151px;\"></p>\n",
    "\n",
    "<pre><b>输入：</b>grid = [[1,2,0,1],[1,3,3,1],[0,2,5,1]], pricing = [2,3], start = [2,3], k = 2\n",
    "<b>输出：</b>[[2,1],[1,2]]\n",
    "<b>解释：</b>起点为 (2,3) 。\n",
    "价格范围为 [2,3] ，我们可以选择的物品坐标为 (0,1)，(1,1)，(1,2) 和 (2,1) 。\n",
    "这些物品的排名为： \n",
    "- (2,1) 距离为 2 ，价格为 2\n",
    "- (1,2) 距离为 2 ，价格为 3\n",
    "- (1,1) 距离为 3\n",
    "- (0,1) 距离为 4\n",
    "所以，给定价格范围内排名最高的 2 件物品的坐标为 (2,1) 和 (1,2) 。\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 3：</strong></p>\n",
    "\n",
    "<p><img alt=\"\" src=\"https://assets.leetcode.com/uploads/2021/12/30/example3.png\" style=\"width: 149px; height: 150px;\"></p>\n",
    "\n",
    "<pre><b>输入：</b>grid = [[1,1,1],[0,0,1],[2,3,4]], pricing = [2,3], start = [0,0], k = 3\n",
    "<b>输出：</b>[[2,1],[2,0]]\n",
    "<b>解释：</b>起点为 (0,0) 。\n",
    "价格范围为 [2,3] ，我们可以选择的物品坐标为 (2,0) 和 (2,1) 。\n",
    "这些物品的排名为：\n",
    "- (2,1) 距离为 5\n",
    "- (2,0) 距离为 6\n",
    "所以，给定价格范围内排名最高的 2 件物品的坐标为 (2,1) 和 (2,0) 。\n",
    "注意，k = 3 但给定价格范围内只有 2 件物品。\n",
    "</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>m == grid.length</code></li>\n",
    "\t<li><code>n == grid[i].length</code></li>\n",
    "\t<li><code>1 &lt;= m, n &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>1 &lt;= m * n &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>0 &lt;= grid[i][j] &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>pricing.length == 2</code></li>\n",
    "\t<li><code>2 &lt;= low &lt;= high &lt;= 10<sup>5</sup></code></li>\n",
    "\t<li><code>start.length == 2</code></li>\n",
    "\t<li><code>0 &lt;= row &lt;= m - 1</code></li>\n",
    "\t<li><code>0 &lt;= col &lt;= n - 1</code></li>\n",
    "\t<li><code>grid[row][col] &gt; 0</code></li>\n",
    "\t<li><code>1 &lt;= k &lt;= m * n</code></li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [k-highest-ranked-items-within-a-price-range](https://leetcode.cn/problems/k-highest-ranked-items-within-a-price-range/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [k-highest-ranked-items-within-a-price-range](https://leetcode.cn/problems/k-highest-ranked-items-within-a-price-range/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['[[1,2,0,1],[1,3,0,1],[0,2,5,1]]\\n[2,5]\\n[0,0]\\n3', '[[1,2,0,1],[1,3,3,1],[0,2,5,1]]\\n[2,3]\\n[2,3]\\n2', '[[1,1,1],[0,0,1],[2,3,4]]\\n[2,3]\\n[0,0]\\n3']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def highestRankedKItems(self, grid: List[List[int]], pricing: List[int], start: List[int], k: int) -> List[List[int]]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        result, q, arr = [], deque([tuple(start)]), []\n",
    "        if grid[start[0]][start[1]]:\n",
    "            if pricing[0] <= grid[start[0]][start[1]] <= pricing[1]:\n",
    "                result.append(start)\n",
    "                k -= 1\n",
    "            grid[start[0]][start[1]] = 0\n",
    "        while k > 0 and q:\n",
    "            for _ in range(len(q)):\n",
    "                i, j = q.popleft()\n",
    "                for i1, j1 in [(i-1, j), (i, j-1), (i, j+1), (i+1, j)]:\n",
    "                    if 0 <= i1 < m and 0 <= j1 < n and grid[i1][j1]:\n",
    "                        if pricing[0] <= grid[i1][j1] <= pricing[1]:\n",
    "                            arr.append((grid[i1][j1], i1, j1))\n",
    "                            k -= 1\n",
    "                        grid[i1][j1] = 0\n",
    "                        q.append((i1, j1))\n",
    "            arr.sort()\n",
    "            if k < 0:\n",
    "                del arr[k:]\n",
    "            result.extend([i, j] for _, i, j in arr)\n",
    "            arr.clear()\n",
    "        return result\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def highestRankedKItems(self, grid: List[List[int]], pricing: List[int], start: List[int], k: int) -> List[List[int]]:\n",
    "        \n",
    "        DIRS = [(-1,0), (0,-1), (0,1), (1,0)]\n",
    "\n",
    "        # 初始化\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        lower, upper = pricing\n",
    "        i, j = start\n",
    "        deque = collections.deque([(grid[i][j], i, j)])\n",
    "        # visited = set([(i, j)])\n",
    "        grid[i][j] = 0\n",
    "\n",
    "        res = []\n",
    "        while deque:\n",
    "            deque = collections.deque(sorted(deque))    # 基于双端队列对当前步数/距离访问到的元素直接进行排序【2.price, 3.行坐标，4.列坐标】\n",
    "            \n",
    "            for _ in range(len(deque)):                 # 当前步数/距离内访问到的全部元素【可省去对于 1.距离 的排序】\n",
    "                price, i, j = deque.popleft()\n",
    "                \n",
    "                if lower<=price<=upper:\n",
    "                    res.append([i, j])\n",
    "                    if len(res) == k:   # 若已满足k个，直接返回\n",
    "                        return res\n",
    "                \n",
    "                for dx, dy in DIRS:\n",
    "                    x, y = i+dx, j+dy\n",
    "                    # if 0<=x<=m-1 and 0<=y<=n-1 and grid[x][y]!=0 and (x,y) not in visited:\n",
    "                    if 0<=x<=m-1 and 0<=y<=n-1 and grid[x][y]!=0:\n",
    "                        deque.append((grid[x][y], x, y))\n",
    "                        # visited.add((x, y))               # 记录访问过的位置\n",
    "                        grid[x][y] = 0                      # 置访问过的位置其元素为0 【表示一堵墙】\n",
    "\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def highestRankedKItems(self, grid: List[List[int]], pricing: List[int], start: List[int], k: int) -> List[List[int]]:\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        l,u = pricing\n",
    "        sx,sy = start\n",
    "        st = [(sx,sy)]\n",
    "        vis = [[0] * n for i in range(m)]\n",
    "        vis[sx][sy] = 1\n",
    "        if l <= grid[sx][sy] <= u:Res=[[sx,sy]];L = 1\n",
    "        else:Res = [];L = 0\n",
    "        while st:\n",
    "            if L > k:\n",
    "                while L > k:\n",
    "                    Res.pop()\n",
    "                    L -= 1\n",
    "                return Res\n",
    "            temp = st;st = [];q = []\n",
    "            for a,b in temp:\n",
    "                for x,y in (a+1,b),(a-1,b),(a,b+1),(a,b-1):\n",
    "                    if 0 <= x < m and 0 <= y < n and not vis[x][y] and grid[x][y]:\n",
    "                        vis[x][y] = 1\n",
    "                        st.append((x,y))\n",
    "                        if l <= grid[x][y] <= u:heappush(q,[grid[x][y],x,y])\n",
    "            while q:\n",
    "                v,x,y = heappop(q)\n",
    "                Res.append([x,y])\n",
    "                L += 1\n",
    "        return Res "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def highestRankedKItems(self, grid: List[List[int]], pricing: List[int], start: List[int], k: int) -> List[List[int]]:\n",
    "        x, y = start\n",
    "        l, h = pricing\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        q = []\n",
    "        q.append((0,grid[x][y],x,y))\n",
    "        dis = [[inf] * n for _ in range(m)]\n",
    "        dis[x][y] = 0\n",
    "        ans = []\n",
    "        while q:\n",
    "            d, p, x, y = heappop(q)\n",
    "            #print(f'{q}')\n",
    "            # if d > dis[x][y]:\n",
    "            #     continue\n",
    "            if l <= p <= h:\n",
    "                ans.append([x,y])\n",
    "            if len(ans) == k:\n",
    "                break\n",
    "                \n",
    "            for nx, ny in (x+1, y),(x-1,y),(x,y+1),(x,y-1):\n",
    "                if not (0 <= nx < m and 0 <= ny < n): continue\n",
    "                if grid[nx][ny] == 0: continue\n",
    "\n",
    "                if dis[nx][ny] > dis[x][y] + 1:\n",
    "                    dis[nx][ny] = dis[x][y] + 1\n",
    "                    heappush(q, (dis[nx][ny], grid[nx][ny], nx, ny))\n",
    "                \n",
    "        return ans         \n",
    "            \n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def highestRankedKItems(self, grid: List[List[int]], pricing: List[int], start: List[int], k: int) -> List[List[int]]:\n",
    "        x, y = start\n",
    "        l, h = pricing\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        q = []\n",
    "        q.append((0,grid[x][y],x,y))\n",
    "        dis = [[inf] * n for _ in range(m)]\n",
    "        dis[x][y] = 0\n",
    "        ans = []\n",
    "        while q:\n",
    "            d, p, x, y = heappop(q)\n",
    "            #print(f'{q}')\n",
    "            if d > dis[x][y]:\n",
    "                continue\n",
    "            if l <= p <= h:\n",
    "                ans.append([x,y])\n",
    "            if len(ans) == k:\n",
    "                break\n",
    "                \n",
    "            for nx, ny in (x+1, y),(x-1,y),(x,y+1),(x,y-1):\n",
    "                if not (0 <= nx < m and 0 <= ny < n): continue\n",
    "                if grid[nx][ny] == 0: continue\n",
    "\n",
    "                if dis[nx][ny] > dis[x][y] + 1:\n",
    "                    dis[nx][ny] = dis[x][y] + 1\n",
    "                    heappush(q, (dis[nx][ny], grid[nx][ny], nx, ny))\n",
    "                \n",
    "        return ans         \n",
    "            \n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def highestRankedKItems(self, grid: List[List[int]], pricing: List[int], start: List[int], k: int) -> List[List[int]]:\n",
    "        \n",
    "        dx = [1, -1, 0, 0]\n",
    "        dy = [0, 0, 1, -1]\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        visit = [[True] * n for _ in range(m)]\n",
    "        visit[start[0]][start[1]] = False\n",
    "        low, high = pricing\n",
    "        queue = [start]\n",
    "        steps = 0\n",
    "        h = []\n",
    "        while queue:\n",
    "            next_queue = []\n",
    "            for i, j in queue:\n",
    "                if grid[i][j] >= low and grid[i][j] <= high:\n",
    "                    heappush(h, (steps, grid[i][j], i, j))\n",
    "                for ii in range(4):\n",
    "                    x = i + dx[ii]\n",
    "                    y = j + dy[ii]\n",
    "                    if 0 <= x < m and 0 <= y < n and grid[x][y] > 0 and visit[x][y]:\n",
    "                        next_queue.append((x, y))\n",
    "                        visit[x][y] = False\n",
    "            queue = next_queue\n",
    "            steps += 1\n",
    "        ans = []\n",
    "        while h and k > 0:\n",
    "            _, _, x, y = heappop(h)\n",
    "            ans.append([x, y])\n",
    "            k -= 1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def highestRankedKItems(self, grid: List[List[int]], pricing: List[int], start: List[int], k: int) -> List[List[int]]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        minp, maxp = pricing[0], pricing[1]\n",
    "        ans = []\n",
    "        sx, sy = start[0], start[1]\n",
    "        if minp <= grid[sx][sy] <= maxp:\n",
    "            ans.append((0, grid[sx][sy], sx, sy))\n",
    "\n",
    "        q = deque([(sx, sy, 0)])\n",
    "        grid[sx][sy] = 0\n",
    "\n",
    "        while q:\n",
    "            x, y, d = q.popleft()\n",
    "            for nx, ny in ((x - 1, y), (x, y - 1), (x, y + 1), (x + 1, y)):\n",
    "                # 无法通过的情况\n",
    "                if nx < 0 or nx >= m or ny < 0 or ny >= n or grid[nx][ny] == 0:\n",
    "                    continue\n",
    "                \n",
    "                # 空格子或者不在自己范围内的格子\n",
    "                if minp <= grid[nx][ny] <= maxp:\n",
    "                    ans.append((d + 1, grid[nx][ny], nx, ny))\n",
    "                q.append((nx, ny, d + 1))\n",
    "                grid[nx][ny] = 0\n",
    "        \n",
    "        ans.sort()\n",
    "        ans = [item[2:] for item in ans][:k]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def highestRankedKItems(self, grid: List[List[int]], pricing: List[int], start: List[int], k: int) -> List[List[int]]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        minp, maxp = pricing[0], pricing[1]\n",
    "        ans = []\n",
    "        sx, sy = start[0], start[1]\n",
    "        if minp <= grid[sx][sy] <= maxp:\n",
    "            ans.append((0, grid[sx][sy], sx, sy))\n",
    "\n",
    "        q = deque([(sx, sy, 0)])\n",
    "        grid[sx][sy] = 0\n",
    "\n",
    "        while q:\n",
    "            x, y, d = q.popleft()\n",
    "            for nx, ny in ((x - 1, y), (x, y - 1), (x, y + 1), (x + 1, y)):\n",
    "                # 无法通过的情况\n",
    "                if nx < 0 or nx >= m or ny < 0 or ny >= n or grid[nx][ny] == 0:\n",
    "                    continue\n",
    "                # 空格子或者不在自己范围内的格子\n",
    "                if minp <= grid[nx][ny] <= maxp:\n",
    "                    ans.append((d + 1, grid[nx][ny], nx, ny))\n",
    "                q.append((nx, ny, d + 1))\n",
    "                grid[nx][ny] = 0\n",
    "        \n",
    "        ans.sort()\n",
    "        ans = [item[2:] for item in ans][:k]\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def highestRankedKItems(self, grid: List[List[int]], pricing: List[int], start: List[int], k: int) -> List[List[int]]:\r\n",
    "        ans = []\r\n",
    "        m, n = len(grid), len(grid[0])\r\n",
    "        low, high = pricing\r\n",
    "        sx, sy = start\r\n",
    "        vis = {(sx, sy)}\r\n",
    "        q = [(sx, sy)]\r\n",
    "        while q:  # 分层 BFS\r\n",
    "            # 此时 q 内所有元素到起点的距离均相同，因此按照题目中的第 2~4 关键字排序后，就可以将价格在 [low,high] 内的位置加入答案\r\n",
    "            q.sort(key=lambda p: (grid[p[0]][p[1]], p))\r\n",
    "            ans.extend(p for p in q if low <= grid[p[0]][p[1]] <= high)\r\n",
    "            if len(ans) >= k: return ans[:k]\r\n",
    "            tmp = q\r\n",
    "            q = []\r\n",
    "            for i, j in tmp:\r\n",
    "                for x, y in (i, j - 1), (i, j + 1), (i - 1, j), (i + 1, j):\r\n",
    "                    if 0 <= x < m and 0 <= y < n and grid[x][y] and (x, y) not in vis:\r\n",
    "                        vis.add((x, y))\r\n",
    "                        q.append((x, y))\r\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def highestRankedKItems(self, grid: List[List[int]], pricing: List[int], start: List[int], k: int) -> List[List[int]]:\n",
    "        ans = []\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        low, high = pricing\n",
    "        sx, sy = start\n",
    "        vis = {(sx, sy)}\n",
    "        q = [(sx, sy)]\n",
    "        while q:  # 分层 BFS\n",
    "            # 此时 q 内所有元素到起点的距离均相同，因此按照题目中的第 2~4 关键字排序后，就可以将价格在 [low,high] 内的位置加入答案\n",
    "            q.sort(key=lambda p: (grid[p[0]][p[1]], p))\n",
    "            ans.extend(p for p in q if low <= grid[p[0]][p[1]] <= high)\n",
    "            if len(ans) >= k: return ans[:k]\n",
    "            tmp = q\n",
    "            q = []\n",
    "            for i, j in tmp:\n",
    "                for x, y in (i, j - 1), (i, j + 1), (i - 1, j), (i + 1, j):\n",
    "                    if 0 <= x < m and 0 <= y < n and grid[x][y] and (x, y) not in vis:\n",
    "                        vis.add((x, y))\n",
    "                        q.append((x, y))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def highestRankedKItems(self, grid: List[List[int]], pricing: List[int], start: List[int], k: int) -> List[List[int]]:\n",
    "        # 分层bfs 迭代加深\n",
    "        # 每次bfs时向外扩展一层，然后对扩展出的这些位置排序，将价格在[low,high]中的物品位置加入答案\n",
    "        ans = []\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        low, high = pricing\n",
    "        sx, sy = start\n",
    "        vis = {(sx, sy)}\n",
    "        q= [(sx, sy)]\n",
    "        while q: # 分层bfs\n",
    "            # 此时q内所有元素到起点的距离相同，因此按照关键字排序后，既可以将价格在[low, high]内的位置加入答案\n",
    "            q.sort(key = lambda p: (grid[p[0]][p[1]], p))\n",
    "            ans.extend(p for p in q if low <= grid[p[0]][p[1]] <= high)\n",
    "            if len(ans) >= k: return ans[:k]\n",
    "            tmp = q\n",
    "            q = []\n",
    "            for i, j in tmp:\n",
    "                for x, y in (i, j - 1), (i, j + 1), (i - 1, j), (i + 1, j):\n",
    "                    if 0 <= x < m and 0 <= y < n and grid[x][y] and (x, y) not in vis:\n",
    "                        vis.add((x, y))\n",
    "                        q.append((x, y))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "\n",
    "    def highestRankedKItems(self, grid: List[List[int]], pricing: List[int], start: List[int], k: int) -> List[List[int]]:\n",
    "\n",
    "        ans = []\n",
    "\n",
    "        m, n = len(grid), len(grid[0])\n",
    "\n",
    "        low, high = pricing\n",
    "\n",
    "        sx, sy = start\n",
    "\n",
    "        vis = {(sx, sy)}\n",
    "\n",
    "        q = [(sx, sy)]\n",
    "\n",
    "        while q:  # 分层 BFS\n",
    "\n",
    "            # 此时 q 内所有元素到起点的距离均相同，因此按照题目中的第 2~4 关键字排序后，就可以将价格在 [low,high] 内的位置加入答案\n",
    "\n",
    "            q.sort(key=lambda p: (grid[p[0]][p[1]], p))\n",
    "\n",
    "            ans.extend(p for p in q if low <= grid[p[0]][p[1]] <= high)\n",
    "\n",
    "            if len(ans) >= k: return ans[:k]\n",
    "\n",
    "            tmp = q\n",
    "\n",
    "            q = []\n",
    "\n",
    "            for i, j in tmp:\n",
    "\n",
    "                for x, y in (i, j - 1), (i, j + 1), (i - 1, j), (i + 1, j):\n",
    "\n",
    "                    if 0 <= x < m and 0 <= y < n and grid[x][y] and (x, y) not in vis:\n",
    "\n",
    "                        vis.add((x, y))\n",
    "\n",
    "                        q.append((x, y))\n",
    "\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def highestRankedKItems(self, grid: List[List[int]], pricing: List[int], start: List[int], k: int) -> List[List[int]]:\n",
    "        ans = []\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        low, high = pricing\n",
    "        sx, sy = start\n",
    "        vis = {(sx, sy)}\n",
    "        q = [(sx, sy)]\n",
    "        while q:  # 分层 BFS\n",
    "            # 此时 q 内所有元素到起点的距离均相同，因此按照题目中的第 2~4 关键字排序后，就可以将价格在 [low,high] 内的位置加入答案\n",
    "            q.sort(key=lambda p: (grid[p[0]][p[1]], p))\n",
    "            ans.extend(p for p in q if low <= grid[p[0]][p[1]] <= high)\n",
    "            if len(ans) >= k: return ans[:k]\n",
    "            tmp = q\n",
    "            q = []\n",
    "            for i, j in tmp:\n",
    "                for x, y in (i, j - 1), (i, j + 1), (i - 1, j), (i + 1, j):\n",
    "                    if 0 <= x < m and 0 <= y < n and grid[x][y] and (x, y) not in vis:\n",
    "                        vis.add((x, y))\n",
    "                        q.append((x, y))\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def highestRankedKItems(self, grid: List[List[int]], pricing: List[int], start: List[int], k: int) -> List[List[int]]:\n",
    "        ans = []\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        low, high = pricing\n",
    "        sx, sy = start\n",
    "        vis = {(sx, sy)}\n",
    "        q = [(sx, sy)]\n",
    "        while q:  # 分层 BFS\n",
    "            # 此时 q 内所有元素到起点的距离均相同，因此按照题目中的第 2~4 关键字排序后，就可以将价格在 [low,high] 内的位置加入答案\n",
    "            q.sort(key=lambda p: (grid[p[0]][p[1]], p))\n",
    "            ans.extend(p for p in q if low <= grid[p[0]][p[1]] <= high)\n",
    "            if len(ans) >= k: return ans[:k]\n",
    "            tmp = q\n",
    "            q = []\n",
    "            for i, j in tmp:\n",
    "                for x, y in (i, j - 1), (i, j + 1), (i - 1, j), (i + 1, j):\n",
    "                    if 0 <= x < m and 0 <= y < n and grid[x][y] and (x, y) not in vis:\n",
    "                        vis.add((x, y))\n",
    "                        q.append((x, y))\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from collections import deque\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def highestRankedKItems(self, grid: List[List[int]], pricing: List[int], start: List[int], k: int) -> List[List[int]]:\n",
    "        rol, col = len(grid), len(grid[0])\n",
    "        def explore(x,y):\n",
    "            return [(x-1,y),(x+1,y),(x,y-1),(x,y+1)]\n",
    "        f = lambda x:grid[x[0]][x[1]]\n",
    "        \n",
    "        if f(start) == 0: \n",
    "            return []\n",
    "        result = []\n",
    "        seen = set()\n",
    "        q = deque()\n",
    "        seen.add(tuple(start))\n",
    "        q.append(tuple(start))\n",
    "        if pricing[0] <= f(start) <= pricing[1]:\n",
    "            result.append(start)\n",
    "        sz = 1\n",
    "        while q:\n",
    "            level = []\n",
    "            while sz:\n",
    "                x,y = q.popleft()\n",
    "                sz -= 1\n",
    "                for i in explore(x,y):\n",
    "                    if 0<=i[0]<rol and 0<=i[1]<col and i not in seen and f(i):\n",
    "                        seen.add(i)\n",
    "                        level.append((*i, f(i)))\n",
    "                        q.append(i)\n",
    "            sz = len(q)\n",
    "            # 多级排序 价格，行，列\n",
    "            level = sorted(level, key=lambda x:(x[2], x[0], x[1]))\n",
    "            # 按价格过滤\n",
    "            level = list(filter(lambda x: pricing[0] <= x[2] <= pricing[1] and x[2] != 1, level))\n",
    "            result += list(map(lambda x:[x[0],x[1]], level))\n",
    "            if len(result) >= k:\n",
    "                return result[:k]\n",
    "        return result\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def highestRankedKItems(self, grid: List[List[int]], pricing: List[int], start: List[int], k: int) -> List[List[int]]:\n",
    "        res_list = []\n",
    "        vis = {(start[0], start[1])}\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        low, high = pricing[0], pricing[1]\n",
    "        \n",
    "        q = [(start[0], start[1])]\n",
    "        while q:\n",
    "            q.sort(key = lambda p:(grid[p[0]][p[1]], p))\n",
    "            res_list.extend(p for p in q if low <= grid[p[0]][p[1]] <= high)\n",
    "            if len(res_list) >= k: return res_list[:k]\n",
    "            tmp = q\n",
    "            q = []\n",
    "            for i, j in tmp:\n",
    "                for ni, nj in (i, j - 1), (i, j + 1), (i - 1, j), (i + 1, j):\n",
    "                    if 0 <= ni < m and 0 <= nj < n and grid[ni][nj] != 0 and (ni, nj) not in vis:\n",
    "                        vis.add((ni, nj))\n",
    "                        q.append((ni, nj))\n",
    "        return res_list\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def highestRankedKItems(self, grid: List[List[int]], pricing: List[int], start: List[int], k: int) -> List[List[int]]:\n",
    "        ans = []\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        low, high = pricing\n",
    "        sx, sy = start\n",
    "        q = [(sx,sy)]\n",
    "        visit = {(sx,sy)}\n",
    "        while q:\n",
    "            q.sort(key = lambda p: (grid[p[0]][p[1]], p))\n",
    "            ans.extend((x,y) for x, y in q if low<= grid[x][y] <= high)\n",
    "            if len(ans) >= k:\n",
    "                return ans[0:k]\n",
    "            tmp = q\n",
    "            q = []\n",
    "            for x, y in tmp:\n",
    "                for nx, ny in (x+1, y), (x-1, y), (x, y+1), (x, y-1):\n",
    "                    if 0 <= nx < m and 0 <= ny < n and (nx,ny) not in visit and grid[nx][ny] != 0:\n",
    "                        visit.add((nx, ny))\n",
    "                        q.append((nx,ny))\n",
    "\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def highestRankedKItems(self, grid: List[List[int]], pricing: List[int], start: List[int], k: int) -> List[List[int]]:\n",
    "        '''\n",
    "        你想知道给定范围 内 且 排名最高 的 k 件物品的 位置 。排名按照优先级从高到低的以下规则制定：\n",
    "\n",
    "        1.距离：定义为从 start 到一件物品的最短路径需要的步数（较近 距离的排名更高）。\n",
    "        2.价格：较低 价格的物品有更高优先级，但只考虑在给定范围之内的价格。\n",
    "        3.行坐标：较小 行坐标的有更高优先级。\n",
    "        4.列坐标：较小 列坐标的有更高优先级。\n",
    "        广度优先搜索\n",
    "        '''\n",
    "\n",
    "        ans = []\n",
    "        m,n = len(grid), len(grid[0])\n",
    "        low, high = pricing\n",
    "        sx, sy = start\n",
    "        vis = {(sx, sy)}\n",
    "        q = [(sx, sy)]\n",
    "        while q: # 分层 BFS\n",
    "            # 此时 q 内所有元素到起点的距离均相同，因此按照题目中的第 2~4 关键字排序后，就可以将价格在 [low,high] 内的位置加入答案\n",
    "            # 按2~4关键字排序\n",
    "            q.sort(key=lambda p:(grid[p[0]][p[1]], p))\n",
    "            # 价格加入答案\n",
    "            ans.extend(p for p in q if low <= grid[p[0]][p[1]] <= high)\n",
    "            # 如果答案数量大于k，返回\n",
    "            if len(ans) >= k:\n",
    "                return ans[:k]\n",
    "            tmp = q # 当前层的坐标保存到tmp中\n",
    "            q = [] # 对每一层进行初始化\n",
    "            for i,j in tmp:\n",
    "                for x,y in (i,j-1), (i,j+1), (i-1,j), (i+1,j):\n",
    "                    if 0 <= x < m and 0 <= y < n and grid[x][y] and (x,y) not in vis:\n",
    "                        vis.add((x,y))\n",
    "                        q.append((x,y))\n",
    "        return ans\n",
    "\n",
    " \n",
    "\n",
    "\n",
    "\n",
    "\n",
    "# 作者：灵茶山艾府\n",
    "# 链接：https://leetcode.cn/problems/k-highest-ranked-items-within-a-price-range/solutions/1226661/fen-ceng-bfs-de-tong-shi-pai-xu-by-endle-ash6/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def highestRankedKItems(self, grid: List[List[int]], pricing: List[int], start: List[int], k: int) -> List[List[int]]:\n",
    "        items = []\n",
    "        # 特殊情况\n",
    "        if pricing[0] <= grid[start[0]][start[1]] <= pricing[1]:\n",
    "            items.append((0,grid[start[0]][start[1]],start[0],start[1]))\n",
    "        m,n = len(grid),len(grid[0])\n",
    "        # 核心思想 BFS\n",
    "        q = deque([(start[0],start[1],0)])\n",
    "        grid[start[0]][start[1]] = 0\n",
    "        while q:\n",
    "            x,y,d = q.popleft()\n",
    "            for i,j in (x-1,y),(x+1,y),(x,y-1),(x,y+1):\n",
    "                if 0 <= i < m and 0 <= j < n and grid[i][j] > 0:\n",
    "                    if pricing[0] <= grid[i][j] <= pricing[1]:\n",
    "                        items.append((d+1,grid[i][j],i,j))\n",
    "                    q.append((i,j,d+1))\n",
    "                    grid[i][j] = 0\n",
    "        items.sort()\n",
    "        res = [item[2:] for item in items][:k]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def highestRankedKItems(self, grid: List[List[int]], pricing: List[int], start: List[int], k: int) -> List[List[int]]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        ans = []\n",
    "        minp, maxp = pricing[0], pricing[1]\n",
    "        x0, y0 = start[0], start[1]\n",
    "\n",
    "        q = deque([(x0, y0, 0)])\n",
    "        if minp <= grid[x0][y0] <= maxp:\n",
    "            ans.append((0, grid[x0][y0], x0, y0))\n",
    "        grid[x0][y0] = 0\n",
    "        \n",
    "        while q:\n",
    "            x, y, d = q.popleft()\n",
    "            for nx, ny in ((x + 1, y), (x - 1, y), (x, y + 1), (x, y-1)):\n",
    "                # 出界或者墙或者访问过\n",
    "                if nx < 0 or nx >= m or ny < 0 or ny >= n or grid[nx][ny] == 0:\n",
    "                    continue\n",
    "                # 空或者其他有值的情况\n",
    "                q.append((nx, ny, d + 1))\n",
    "                if minp <= grid[nx][ny] <= maxp:\n",
    "                    ans.append((d + 1, grid[nx][ny], nx, ny))\n",
    "                grid[nx][ny] = 0\n",
    "                \n",
    "        ans.sort()\n",
    "        ans = [item[2:] for item in ans][:k]\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def highestRankedKItems(self, grid: List[List[int]], pricing: List[int], start: List[int], k: int) -> List[List[int]]:\n",
    "        heap = []\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        low, high = pricing[0], pricing[1]\n",
    "        visited = [[False] * n for _ in range(m)]\n",
    "        visited[start[0]][start[1]] = True\n",
    "        q = deque([(start[0], start[1], 0)])\n",
    "\n",
    "        while q:\n",
    "            x, y, distance = q.popleft()\n",
    "            price = grid[x][y]\n",
    "            if len(heap) >= k and -heap[0][0] < distance:\n",
    "                break\n",
    "\n",
    "            if low <= price <= high:\n",
    "                heapq.heappush(heap, (-distance, -price, -x, -y))\n",
    "                if len(heap) > k:\n",
    "                    heapq.heappop(heap)\n",
    "\n",
    "            for x1, y1 in [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]:\n",
    "                if x1 < 0 or y1 < 0 or x1 == m or y1 == n:\n",
    "                    continue\n",
    "                \n",
    "                if grid[x1][y1] != 0 and not visited[x1][y1]:\n",
    "                    q.append((x1, y1, distance + 1))\n",
    "                    visited[x1][y1] = True\n",
    "        \n",
    "        result = []\n",
    "        while heap:\n",
    "            _, _, x, y = heapq.heappop(heap)\n",
    "            result.append([-x, -y])\n",
    "        \n",
    "        return result[::-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def highestRankedKItems(self, grid: List[List[int]], pricing: List[int], start: List[int], k: int) -> List[List[int]]:\n",
    "        heap = []\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        low, high = pricing[0], pricing[1]\n",
    "        visited = [[False] * n for _ in range(m)]\n",
    "        visited[start[0]][start[1]] = True\n",
    "        q = deque([(start[0], start[1], 0)])\n",
    "\n",
    "        while q:\n",
    "            x, y, distance = q.popleft()\n",
    "            price = grid[x][y]\n",
    "            if low <= price <= high:\n",
    "                heapq.heappush(heap, (-distance, -price, -x, -y))\n",
    "                if len(heap) > k:\n",
    "                    heapq.heappop(heap)\n",
    "\n",
    "            for x1, y1 in [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]:\n",
    "                if x1 < 0 or y1 < 0 or x1 == m or y1 == n:\n",
    "                    continue\n",
    "                \n",
    "                if grid[x1][y1] != 0 and not visited[x1][y1]:\n",
    "                    q.append((x1, y1, distance + 1))\n",
    "                    visited[x1][y1] = True\n",
    "        \n",
    "        result = []\n",
    "        while heap:\n",
    "            _, _, x, y = heapq.heappop(heap)\n",
    "            result.append([-x, -y])\n",
    "        \n",
    "        return result[::-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def highestRankedKItems(self, grid: List[List[int]], pricing: List[int], start: List[int], k: int) -> List[List[int]]:\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        low, high = pricing\n",
    "        heap = []\n",
    "        q = collections.deque([(start[0], start[1], 0)])\n",
    "        visited = [[False] * n for _ in range(m)]\n",
    "        visited[start[0]][start[1]] = True\n",
    "\n",
    "        while q:\n",
    "            x, y, distance = q.popleft()\n",
    "            price = grid[x][y]\n",
    "            if low <= price <= high:\n",
    "                heapq.heappush(heap, (-distance, -price, -x, -y))\n",
    "                if len(heap) > k:\n",
    "                    heapq.heappop(heap)\n",
    "\n",
    "            for newX, newY in [(x+1, y), (x-1, y), (x, y+1), (x, y-1)]:\n",
    "                if newX < 0 or newY < 0 or newX == m or newY == n:\n",
    "                    continue\n",
    "\n",
    "                if not visited[newX][newY] and grid[newX][newY] != 0:\n",
    "                    visited[newX][newY] = True\n",
    "                    q.append((newX, newY, distance + 1))\n",
    "        \n",
    "        result = []\n",
    "        while heap:\n",
    "            _, _, negX, negY = heapq.heappop(heap)\n",
    "            result.append([-negX, -negY])\n",
    "        return result[::-1]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def highestRankedKItems(self, grid: List[List[int]], pricing: List[int], start: List[int], k: int) -> List[List[int]]:\n",
    "        #直接对四元组排序的了，调用默认的sort方便得很\n",
    "        m,n =len(grid),len(grid[0])\n",
    "        ans=[]\n",
    "        \n",
    "        low,high=pricing[0],pricing[1]\n",
    "        x,y=start[0],start[1]\n",
    "        q=[]\n",
    "        q.append((x,y))\n",
    "        if low<=grid[x][y]<=high:\n",
    "            ans.append((0,grid[x][y],x,y))\n",
    "\n",
    "        dist=0\n",
    "        vis=[[False]*n for _ in range(m)]\n",
    "        vis[x][y]=True\n",
    "        while q:\n",
    "            tmp=[]\n",
    "            flag=True\n",
    "            while q:\n",
    "                x,y =q.pop()  \n",
    "                for i,j in (x-1,y),(x+1,y),(x,y-1),(x,y+1):\n",
    "                    if 0<=i<m and 0<=j<n and not vis[i][j] and grid[i][j]:\n",
    "                        if flag:\n",
    "                            dist+=1\n",
    "                            flag=False\n",
    "                        p=grid[i][j]\n",
    "                        vis[i][j]=True\n",
    "                        if low<=p<=high:\n",
    "                            ans.append((dist,p,i,j))\n",
    "                        tmp.append((i,j))\n",
    "            q=tmp\n",
    "        ans.sort()  \n",
    "        res=[]\n",
    "        for x in ans[:k]:\n",
    "            _,_,i,j=x\n",
    "            res.append([i,j])\n",
    "        return res\n",
    "\n",
    "                        \n",
    "                        \n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def highestRankedKItems(self, grid: List[List[int]], pricing: List[int], start: List[int], k: int) -> List[List[int]]:\n",
    "        # bfs 搜索\n",
    "        # 搜索之后排序就好了 \n",
    "        m,n = len(grid), len(grid[0])\n",
    "        arr = []\n",
    "        vis = [[False] * n for _ in range(m)]\n",
    "        vis[start[0]][start[1]] = True\n",
    "        q = [(start[0], start[1])]\n",
    "        step = 0\n",
    "        while q:\n",
    "            tmp = q \n",
    "            q = []\n",
    "            for x, y in tmp:\n",
    "                vis[x][y] = True \n",
    "                if grid[x][y] == 0: continue \n",
    "                elif grid[x][y] >= 2:\n",
    "                    if pricing[0] <= grid[x][y] <= pricing[1]:\n",
    "                        arr.append((x, y, grid[x][y], step))\n",
    "                for nx, ny in (x - 1, y), (x, y - 1), (x, y + 1), (x + 1, y):\n",
    "                    if 0 <= nx < m and 0 <= ny < n and not vis[nx][ny]:\n",
    "                        vis[nx][ny] = True\n",
    "                        q.append((nx, ny)) \n",
    "            step += 1\n",
    "        \n",
    "        arr.sort(key= lambda x:[x[3], x[2], x[0], x[1]])\n",
    "        return  [[x[0], x[1]] for x in arr[:k]]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    def highestRankedKItems(self, grid: List[List[int]], pricing: List[int], start: List[int], k: int) -> List[List[int]]:\r\n",
    "        # bfs 搜索\r\n",
    "        # 搜索之后排序就好了 \r\n",
    "        m,n = len(grid), len(grid[0])\r\n",
    "        arr = []\r\n",
    "        vis = [[False] * n for _ in range(m)]\r\n",
    "        vis[start[0]][start[1]] = True\r\n",
    "        q = [(start[0], start[1])]\r\n",
    "        step = 0\r\n",
    "        while q:\r\n",
    "            tmp = q \r\n",
    "            q = []\r\n",
    "            for x, y in tmp:\r\n",
    "                vis[x][y] = True \r\n",
    "                if grid[x][y] == 0: continue \r\n",
    "                elif grid[x][y] >= 2:\r\n",
    "                    if pricing[0] <= grid[x][y] <= pricing[1]:\r\n",
    "                        arr.append((x, y, grid[x][y], step))\r\n",
    "                for nx, ny in (x - 1, y), (x, y - 1), (x, y + 1), (x + 1, y):\r\n",
    "                    if 0 <= nx < m and 0 <= ny < n and not vis[nx][ny]:\r\n",
    "                        vis[nx][ny] = True\r\n",
    "                        q.append((nx, ny)) \r\n",
    "            step += 1\r\n",
    "        \r\n",
    "        arr.sort(key= lambda x:[x[3], x[2],x[0], x[1]])\r\n",
    "        return  [[x[0], x[1]] for x in arr[:k]]\r\n",
    "\r\n",
    "\r\n",
    "\r\n",
    "\r\n",
    "\r\n",
    "\r\n",
    "        \r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def highestRankedKItems(self, grid: List[List[int]], pricing: List[int], start: List[int], k: int) -> List[List[int]]:\n",
    "        q = [start]\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        vst = [[0] * n for _ in range(m)]\n",
    "        step = [[0] * n for _ in range(m)]\n",
    "        x, y = start\n",
    "        vst[x][y] = 1\n",
    "        ret = []\n",
    "        if pricing[0] <= grid[x][y] <= pricing[1]:\n",
    "            ret.append([x, y])\n",
    "        dirs = ((-1, 0), (0, -1), (0, 1), (1, 0))\n",
    "        cnt = 0\n",
    "        while q:\n",
    "            cnt += 1\n",
    "            tmp = q\n",
    "            q = []\n",
    "            item = []\n",
    "            for x, y in tmp:\n",
    "                for dx, dy in dirs:\n",
    "                    x2, y2 = x + dx, y + dy\n",
    "                    if 0 <= x2 < m and 0 <= y2 < n and grid[x2][y2] != 0 and not vst[x2][y2]:\n",
    "                        vst[x2][y2] = True\n",
    "                        q.append([x2, y2])\n",
    "                        if pricing[0] <= grid[x2][y2] <= pricing[1]:\n",
    "                            item.append([x2, y2])\n",
    "                            step[x2][y2] = cnt\n",
    "            # item.sort(key=lambda xy: (grid[xy[0]][xy[1]], xy[0], xy[1]))\n",
    "            ret += item\n",
    "        ret.sort(key=lambda xy: (step[xy[0]][xy[1]], grid[xy[0]][xy[1]], xy[0], xy[1]))\n",
    "        return ret[:k]\n",
    "            \n",
    "            "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "from queue import Queue\n",
    "LEFT, RIGHT, UP, DOWN = (0, -1), (0, 1), (-1, 0), (1, 0)\n",
    "\n",
    "class Solution:\n",
    "    def highestRankedKItems(self, grid: List[List[int]], pricing: List[int], start: List[int], k: int) -> List[\n",
    "        List[int]]:\n",
    "        que, ret = [], []\n",
    "        step = 0\n",
    "        q = Queue()\n",
    "        q.put((start[0], start[1], 0))\n",
    "        vis = set()\n",
    "        vis.add((start[0], start[1]))\n",
    "        n, m = len(grid), len(grid[0])\n",
    "        if pricing[0] <= grid[start[0]][start[1]] <= pricing[1]:\n",
    "            ret.append(start)\n",
    "        while not q.empty():\n",
    "            x, y, s = q.get()\n",
    "            if s > step:\n",
    "                step = s\n",
    "                while len(ret) < k and len(que) > 0:\n",
    "                    ret.append(heapq.heappop(que)[1:])\n",
    "            if len(ret) >= k: return ret\n",
    "            for dx, dy in (LEFT, UP, DOWN, RIGHT):\n",
    "                tx = x + dx\n",
    "                ty = y + dy\n",
    "                if 0 <= tx < n and 0 <= ty < m and grid[tx][ty] != 0:\n",
    "                    if (tx, ty) not in vis:\n",
    "                        vis.add((tx, ty))\n",
    "                        q.put((tx, ty, s + 1))\n",
    "                        if pricing[0] <= grid[tx][ty] <= pricing[1]:\n",
    "                            heapq.heappush(que, [grid[tx][ty], tx, ty])\n",
    "        return ret\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def highestRankedKItems(self, grid: List[List[int]], pricing: List[int], start: List[int], k: int) -> List[List[int]]:\n",
    "        checked = set()\n",
    "        low, high = pricing[0], pricing[1]\n",
    "        q = {(start[0], start[1])}\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        direction = [[-1, 0], [1, 0], [0, -1], [0, 1]]\n",
    "        ret = list()\n",
    "        while q and len(ret) < k:\n",
    "            heap = list()\n",
    "            for x, y in q:\n",
    "                checked.add((x, y))\n",
    "                if low <= grid[x][y] <= high:\n",
    "                    heapq.heappush(heap, (grid[x][y], x, y))\n",
    "            while heap:\n",
    "                key = heapq.heappop(heap)\n",
    "                ret.append([key[1], key[2]])\n",
    "            if len(ret) >= k:\n",
    "                break\n",
    "            new_q = set()\n",
    "            for x, y in q:\n",
    "                for d in direction:\n",
    "                    new_x, new_y = x+d[0], y+d[1]\n",
    "                    if new_x < 0 or new_x >= m or new_y < 0 or new_y >= n or (new_x, new_y) in checked or grid[new_x][new_y] == 0:\n",
    "                        continue\n",
    "                    new_q.add((new_x, new_y))\n",
    "            q = new_q\n",
    "\n",
    "        return ret[:k]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def highestRankedKItems(self, grid: List[List[int]], pricing: List[int], start: List[int], k: int) -> List[List[int]]:\n",
    "        checked = set()\n",
    "        low, high = pricing[0], pricing[1]\n",
    "        q = {(start[0], start[1])}\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        direction = [[-1, 0], [1, 0], [0, -1], [0, 1]]\n",
    "        ret = list()\n",
    "        while q and len(ret) < k:\n",
    "            heap = list()\n",
    "            for x, y in q:\n",
    "                checked.add((x, y))\n",
    "                if low <= grid[x][y] <= high:\n",
    "                    heapq.heappush(heap, (grid[x][y], x, y))\n",
    "            while heap:\n",
    "                key = heapq.heappop(heap)\n",
    "                ret.append([key[1], key[2]])\n",
    "            if len(ret) >= k:\n",
    "                break\n",
    "            new_q = set()\n",
    "            for x, y in q:\n",
    "                for d in direction:\n",
    "                    new_x, new_y = x+d[0], y+d[1]\n",
    "                    if new_x < 0 or new_x >= m or new_y < 0 or new_y >= n or (new_x, new_y) in checked or grid[new_x][new_y] == 0:\n",
    "                        continue\n",
    "                    new_q.add((new_x, new_y))\n",
    "            q = new_q\n",
    "\n",
    "        return ret[:k]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def highestRankedKItems(self, grid: List[List[int]], pricing: List[int], start: List[int], k: int) -> List[List[int]]:\n",
    "        checked = set()\n",
    "        low, high = pricing[0], pricing[1]\n",
    "        q = {(start[0], start[1])}\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        direction = [[-1, 0], [1, 0], [0, -1], [0, 1]]\n",
    "        ret = list()\n",
    "        while q and len(ret) < k:\n",
    "            heap = list()\n",
    "            for x, y in q:\n",
    "                checked.add((x, y))\n",
    "                if low <= grid[x][y] <= high:\n",
    "                    heapq.heappush(heap, (grid[x][y], x, y))\n",
    "            while heap and len(ret) < k:\n",
    "                key = heapq.heappop(heap)\n",
    "                ret.append([key[1], key[2]])\n",
    "            if len(ret) >= k:\n",
    "                break\n",
    "            new_q = set()\n",
    "            for x, y in q:\n",
    "                for d in direction:\n",
    "                    new_x, new_y = x+d[0], y+d[1]\n",
    "                    if new_x < 0 or new_x >= m or new_y < 0 or new_y >= n or (new_x, new_y) in checked or grid[new_x][new_y] == 0:\n",
    "                        continue\n",
    "                    new_q.add((new_x, new_y))\n",
    "            q = new_q\n",
    "\n",
    "        return ret[:k]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def highestRankedKItems(self, grid: List[List[int]], pricing: List[int], start: List[int], k: int) -> List[List[int]]:\n",
    "        items = []\n",
    "        # 核心思想：BFS\n",
    "        # 找出start到其他所有物品的距离（distance,value,i,j）\n",
    "        m,n = len(grid),len(grid[0])\n",
    "\n",
    "        if pricing[0] <= grid[start[0]][start[1]] <= pricing[1]:\n",
    "            items.append([0,grid[start[0]][start[1]],start[0],start[1]])\n",
    "\n",
    "        q = deque([(start[0],start[1],0)])\n",
    "        grid[start[0]][start[1]] = 0\n",
    "        # BFS\n",
    "        while q:\n",
    "            i,j,d = q.popleft()\n",
    "            for x,y in (i-1,j),(i,j-1),(i,j+1),(i+1,j):\n",
    "                if 0 <= x < m and 0 <= y < n and grid[x][y] > 0:\n",
    "                    if pricing[0] <= grid[x][y] <= pricing[1]:\n",
    "                        # 存储起来\n",
    "                        items.append([d+1,grid[x][y],x,y])\n",
    "                    q.append((x,y,d+1))\n",
    "                    grid[x][y] = 0\n",
    "        # 统计结果\n",
    "        items.sort()\n",
    "        res = [item[2:] for item in items][:k]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def highestRankedKItems(self, grid: List[List[int]], pricing: List[int], start: List[int], k: int) -> List[List[int]]:\n",
    "        checked = set()\n",
    "        low, high = pricing[0], pricing[1]\n",
    "        q = {(start[0], start[1])}\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        direction = [[-1, 0], [1, 0], [0, -1], [0, 1]]\n",
    "        ret = list()\n",
    "        while q and len(ret) < k:\n",
    "            heap = list()\n",
    "            for x, y in q:\n",
    "                checked.add((x, y))\n",
    "                if low <= grid[x][y] <= high:\n",
    "                    heapq.heappush(heap, (grid[x][y], x, y))\n",
    "            while heap:\n",
    "                key = heapq.heappop(heap)\n",
    "                ret.append([key[1], key[2]])\n",
    "            new_q = set()\n",
    "            for x, y in q:\n",
    "                for d in direction:\n",
    "                    new_x, new_y = x+d[0], y+d[1]\n",
    "                    if new_x < 0 or new_x >= m or new_y < 0 or new_y >= n or (new_x, new_y) in checked or grid[new_x][new_y] == 0:\n",
    "                        continue\n",
    "                    new_q.add((new_x, new_y))\n",
    "            q = new_q\n",
    "\n",
    "        return ret[:k]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def highestRankedKItems(self, grid: List[List[int]], pricing: List[int], start: List[int], k: int) -> List[List[int]]:\n",
    "        m=len(grid)\n",
    "        n=len(grid[0])\n",
    "        seen=[[0]*n for _ in range(m)]\n",
    "        seen[start[0]][start[1]]=1\n",
    "        q=[[0,grid[start[0]][start[1]], start[0], start[1]]]\n",
    "        x_dir=[0,0,-1,1]\n",
    "        y_dir=[-1,1,0,0]\n",
    "        dist=0\n",
    "        res=[]\n",
    "        if grid[start[0]][start[1]]>1 and grid[start[0]][start[1]]>=pricing[0] and grid[start[0]][start[1]]<=pricing[1]:\n",
    "            res.append([0,grid[start[0]][start[1]], start[0], start[1]])\n",
    "        while q:\n",
    "            size=len(q)\n",
    "            dist+=1\n",
    "            for _ in range(size):\n",
    "                pred, prec, prex, prey=q.pop(0)\n",
    "                for i in range(4):\n",
    "                    tx=prex+x_dir[i]\n",
    "                    ty=prey+y_dir[i]\n",
    "                    if tx>=0 and tx<m and ty>=0 and ty<n and grid[tx][ty]!=0 and seen[tx][ty]==0:\n",
    "                        seen[tx][ty]=1\n",
    "                        q.append([dist, grid[tx][ty], tx, ty])\n",
    "                        if grid[tx][ty]>1 and grid[tx][ty]>=pricing[0] and grid[tx][ty]<=pricing[1]:\n",
    "                            res.append([dist, grid[tx][ty], tx, ty])\n",
    "        res.sort(key=lambda x:(x[0],x[1],x[2],x[3]))\n",
    "        # print(res)\n",
    "        k=min(k, len(res))\n",
    "        ans=[]\n",
    "        for i in range(k):\n",
    "            ans.append([res[i][2], res[i][3]])\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def highestRankedKItems(self, grid: List[List[int]], pricing: List[int], start: List[int], k: int) -> List[List[int]]:\n",
    "       m = len(grid)\n",
    "       n = len(grid[0])\n",
    "       _list = []\n",
    "       q = [[start[0], start[1], 0]]\n",
    "       dirs = [[0, -1], [1, 0], [-1, 0], [0, 1]]\n",
    "       while q:\n",
    "          [x, y, d] = q.pop(0)\n",
    "          if grid[x][y] == 0:\n",
    "             continue\n",
    "          if pricing[1] >= grid[x][y] >= pricing[0]:\n",
    "             _list.append([d, grid[x][y], x, y])\n",
    "          grid[x][y] = 0\n",
    "          for dx, dy in dirs:\n",
    "             nx = x + dx\n",
    "             ny = y + dy\n",
    "             if nx >= 0 and nx < m and ny >= 0 and ny < n and grid[nx][ny] != 0:\n",
    "                q.append([nx, ny, d + 1])\n",
    "       _list.sort(key=lambda o:(o[0], o[1], o[2], o[3]))\n",
    "       res = []\n",
    "       for i in range(min(len(_list), k)):\n",
    "          res.append([_list[i][2], _list[i][3]])\n",
    "       return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def highestRankedKItems(self, grid: List[List[int]], pricing: List[int], start: List[int], k: int) -> List[List[int]]:\n",
    "        m,n=len(grid),len(grid[0])\n",
    "        ll=[[-1,0],[1,0],[0,-1],[0,1]]\n",
    "\n",
    "        q=[[(grid[start[0]][start[1]] if pricing[0]<=grid[start[0]][start[1]]<=pricing[1] else inf),start[0],start[1]]]\n",
    "        ans=[]\n",
    "        visited=set()\n",
    "        visited.add((start[0],start[1]))\n",
    "        while q:\n",
    "            # print(q)\n",
    "            if len(ans)>=k:return ans[:k]\n",
    "            t=len(q)\n",
    "            q.sort()\n",
    "            for i in q:\n",
    "                if i[0]!=inf:\n",
    "                    ans.append(i[1:])\n",
    "\n",
    "            for i in range(t):\n",
    "                temp=q[i][1:]\n",
    "                for ii,jj in ll:\n",
    "                    newi,newj=temp[0]+ii,temp[1]+jj\n",
    "                    if 0<=newi<m and 0<=newj<n and (newi,newj) not in visited and grid[newi][newj]!=0:\n",
    "                        visited.add((newi,newj))\n",
    "                        q.append([(grid[newi][newj] if pricing[0]<=grid[newi][newj]<=pricing[1] else inf),newi,newj])\n",
    "\n",
    "\n",
    "            q=q[t:]\n",
    "\n",
    "\n",
    "        return ans[:k]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def highestRankedKItems(self, grid: List[List[int]], pricing: List[int], start: List[int], k: int) -> List[List[int]]:\n",
    "        items = []   # 感兴趣物品的信息\n",
    "        q = deque([(start[0], start[1], 0)])   # 广度优先搜索队列\n",
    "        if pricing[0] <= grid[start[0]][start[1]] <= pricing[1]:\n",
    "            items.append([0, grid[start[0]][start[1]], start[0], start[1]])\n",
    "        grid[start[0]][start[1]] = 0   # 避免重复遍历\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        dx = [1, 0, -1, 0]\n",
    "        dy = [0, 1, 0, -1]\n",
    "        while q:\n",
    "            x, y, d = q.popleft()\n",
    "            for i in range(4):\n",
    "                # 遍历相邻坐标，并进行对应操作\n",
    "                nx, ny = x + dx[i], y + dy[i]\n",
    "                if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] > 0:\n",
    "                    q.append((nx, ny, d + 1))\n",
    "                    if pricing[0] <= grid[nx][ny] <= pricing[1]:\n",
    "                        items.append([d + 1, grid[nx][ny], nx, ny])\n",
    "                    grid[nx][ny] = 0   # 避免重复遍历\n",
    "        items.sort()   # 按照优先级从高到低排序\n",
    "        res = [item[2:] for item in items][:k]   # 排名最高 k 件物品的坐标\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def highestRankedKItems(self, grid: List[List[int]], pricing: List[int], start: List[int], k: int) -> List[List[int]]:\n",
    "        items = [] #感兴趣的物品信息\n",
    "        queue = collections.deque([(start[0], start[1], 0)]) # 广度优先搜索队列\n",
    "        if pricing[0] <= grid[start[0]][start[1]] <= pricing[1]:\n",
    "            items.append([0, grid[start[0]][start[1]], start[0], start[1]])\n",
    "        grid[start[0]][start[1]] = 0\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        dirs = [[0,1],[1,0],[0,-1],[-1,0]]\n",
    "        while queue:\n",
    "            i, j, d = queue.popleft()\n",
    "            for di in dirs:\n",
    "                new_i = i + di[0]\n",
    "                new_j = j + di[1]\n",
    "                if 0 <= new_i < m and 0 <= new_j < n and grid[new_i][new_j] > 0:\n",
    "                    queue.append((new_i, new_j, d+1))\n",
    "                    if pricing[0] <= grid[new_i][new_j] <= pricing[1]:\n",
    "                        items.append([d+1, grid[new_i][new_j], new_i, new_j])\n",
    "                    grid[new_i][new_j] = 0\n",
    "        items.sort()\n",
    "        res = [item[2:] for item in items][:k]\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def highestRankedKItems(self, grid: List[List[int]], pricing: List[int], start: List[int], k: int) -> List[List[int]]:\n",
    "        items = []\n",
    "        q = deque([(start[0],start[1],0)])\n",
    "        if(pricing[0] <= grid[start[0]][start[1]] <= pricing[1]):\n",
    "            items.append([0,grid[start[0]][start[1]],start[0],start[1]])\n",
    "        grid[start[0]][start[1]] = 0\n",
    "        m = len(grid)\n",
    "        n = len(grid[0])\n",
    "        dx = [-1,0,1,0]\n",
    "        dy = [0,-1,0,1]\n",
    "        while q:\n",
    "            x,y,d = q.popleft()\n",
    "            for i in range(4):\n",
    "                nx = x + dx[i]\n",
    "                ny = y + dy[i]\n",
    "                if 0 <= nx < m and 0 <= ny < n and grid[nx][ny] > 0:\n",
    "                    q.append([nx,ny,d+ 1])\n",
    "                    if pricing[0] <= grid[nx][ny] <= pricing[1]:\n",
    "                        items.append([d + 1,grid[nx][ny],nx,ny])\n",
    "                    grid[nx][ny] = 0 # 标记\n",
    "        items.sort()\n",
    "        res = [item[2:] for item in items]\n",
    "        return res[:k]\n",
    "                        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def highestRankedKItems(self, grid: List[List[int]], pricing: List[int], start: List[int], k: int) -> List[List[int]]:\n",
    "        queue=deque([(start[0],start[1],0)])\n",
    "        possible=[]\n",
    "        m=len(grid)\n",
    "        n=len(grid[0])\n",
    "        visited=set()\n",
    "\n",
    "        while len(queue)>0:\n",
    "            now=queue.popleft()\n",
    "            if now[0]<0 or now[0]>=m or now[1]<0 or now[1]>=n:\n",
    "                continue\n",
    "            if grid[now[0]][now[1]]==0:\n",
    "                continue\n",
    "            key=(now[0],now[1])\n",
    "            if key in visited:\n",
    "                continue\n",
    "            visited.add(key)\n",
    "            p=grid[now[0]][now[1]]\n",
    "            if p>=pricing[0] and p<=pricing[1]:\n",
    "                possible.append((now[2],p,now[0],now[1]))\n",
    "            \n",
    "            queue.append((now[0]+1,now[1],now[2]+1))\n",
    "            queue.append((now[0]-1,now[1],now[2]+1))\n",
    "            queue.append((now[0],now[1]+1,now[2]+1))\n",
    "            queue.append((now[0],now[1]-1,now[2]+1))\n",
    "\n",
    "        possible.sort()\n",
    "        return [p[2:] for p in possible[:k]]\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def highestRankedKItems(self, grid: List[List[int]], pricing: List[int], start: List[int], k: int) -> List[List[int]]:\n",
    "        '''bfs'''\n",
    "        ans = []\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        seen = set()\n",
    "        seen.add((start[0], start[1]))\n",
    "        \n",
    "        queue = [(start, 0)]\n",
    "        while queue:\n",
    "            ele = queue.pop(0)\n",
    "            row, col, step = ele[0][0], ele[0][1], ele[1]\n",
    "            tmp = grid[row][col]\n",
    "            \n",
    "            if tmp != 1 and pricing[0] <= tmp <= pricing[1]:\n",
    "                ans.append((step, tmp, row, col))\n",
    "            \n",
    "            for i, j in ((row, col+1), (row, col-1), (row+1, col), (row-1, col)):\n",
    "                if 0<=i<m and 0<=j<n and grid[i][j] and (i,j) not in seen:\n",
    "                    queue.append(((i,j), step+1))\n",
    "                    seen.add((i,j))\n",
    "        \n",
    "        ans.sort()\n",
    "        return [[x,y] for _,_,x,y in ans[:k]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def highestRankedKItems(self, grid: List[List[int]], pricing: List[int], start: List[int], k: int) -> List[List[int]]:\n",
    "        # 简单的bfs\n",
    "        m, n = len(grid), len(grid[0])\n",
    "        low, high = pricing\n",
    "        if grid[start[0]][start[1]] == 0:\n",
    "            return []\n",
    "        \n",
    "        ans = []\n",
    "        cur = [tuple(start)]\n",
    "        vis = {tuple(start)}\n",
    "        step = 0\n",
    "        while cur:\n",
    "            step += 1\n",
    "            nxt = set()\n",
    "            for x, y in cur:\n",
    "                if low <= grid[x][y] <= high:\n",
    "                    ans.append([step, grid[x][y], x, y])\n",
    "                for u, v in (x-1, y), (x+1, y), (x, y-1), (x, y+1):\n",
    "                    if 0 <= u < m and 0 <= v < n and grid[u][v] > 0 and (u, v) not in vis: \n",
    "                        nxt.add((u, v))\n",
    "                        vis.add((u, v))\n",
    "            cur = list(nxt)\n",
    "\n",
    "        \n",
    "        ans.sort()\n",
    "        ans = [[x, y] for s, p, x, y in ans[:k]]\n",
    "        return ans\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def highestRankedKItems(self, grid: List[List[int]], pricing: List[int], start: List[int], k: int) -> List[List[int]]:\n",
    "\n",
    "        res = []\n",
    "        \n",
    "        nodes = deque([start])\n",
    "        \n",
    "        dirs = [\n",
    "            [1, 0],\n",
    "            [-1, 0],\n",
    "            [0, 1],\n",
    "            [0, -1],\n",
    "        ]\n",
    "        visited = set([tuple(start)])\n",
    "        step = 0\n",
    "        if pricing[0] <= grid[start[0]][start[1]] <= pricing[1]:\n",
    "            res.append([0, grid[start[0]][start[1]], start[0], start[1]])\n",
    "\n",
    "        while nodes:\n",
    "            new_nodes = []\n",
    "            step += 1\n",
    "            for row, col in nodes:\n",
    "                for row_diff, col_diff in dirs:\n",
    "                    new_row = row + row_diff\n",
    "                    new_col = col + col_diff\n",
    "                    if 0 <= new_row < len(grid) and 0 <= new_col < len(grid[row]) and grid[new_row][new_col] != 0 and (new_row, new_col) not in visited:\n",
    "                        visited.add((new_row, new_col))\n",
    "                        new_nodes.append([new_row, new_col])\n",
    "                        if pricing[0] <= grid[new_row][new_col] <= pricing[1]:\n",
    "                            res.append([step, grid[new_row][new_col], new_row, new_col])\n",
    "            nodes = new_nodes\n",
    "            if len(res) == k:\n",
    "                return [[item[2], item[3]] for item in sorted(res)[:k]]\n",
    "        \n",
    "        return [[item[2], item[3]] for item in sorted(res)[:k]]\n",
    "        \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def highestRankedKItems(self, grid: List[List[int]], pricing: List[int], start: List[int], k: int) -> List[List[int]]:\n",
    "\n",
    "        res = []\n",
    "        \n",
    "        nodes = deque([start])\n",
    "        \n",
    "        dirs = [\n",
    "            [1, 0],\n",
    "            [-1, 0],\n",
    "            [0, 1],\n",
    "            [0, -1],\n",
    "        ]\n",
    "        visited = set([tuple(start)])\n",
    "        step = 0\n",
    "        if pricing[0] <= grid[start[0]][start[1]] <= pricing[1]:\n",
    "            res.append([0, grid[start[0]][start[1]], start[0], start[1]])\n",
    "\n",
    "        while nodes:\n",
    "            new_nodes = []\n",
    "            step += 1\n",
    "            for row, col in nodes:\n",
    "                for row_diff, col_diff in dirs:\n",
    "                    new_row = row + row_diff\n",
    "                    new_col = col + col_diff\n",
    "                    if 0 <= new_row < len(grid) and 0 <= new_col < len(grid[row]) and grid[new_row][new_col] != 0 and (new_row, new_col) not in visited:\n",
    "                        visited.add((new_row, new_col))\n",
    "                        new_nodes.append([new_row, new_col])\n",
    "                        if pricing[0] <= grid[new_row][new_col] <= pricing[1]:\n",
    "                            res.append([step, grid[new_row][new_col], new_row, new_col])\n",
    "            nodes = new_nodes\n",
    "            if len(res) >= k:\n",
    "                return [[item[2], item[3]] for item in sorted(res)[:k]]\n",
    "        \n",
    "        return [[item[2], item[3]] for item in sorted(res)[:k]]\n",
    "        \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def highestRankedKItems(self, grid: List[List[int]], pricing: List[int], start: List[int], k: int) -> List[List[int]]:\n",
    "        from collections import deque\n",
    "        m,n =len(grid),len(grid[0])\n",
    "        low,high = pricing[0],pricing[1]\n",
    "        x,y = start[0],start[1]\n",
    "        visited = set()\n",
    "        q = deque([])\n",
    "        q.append([0,grid[x][y],x,y])\n",
    "        visited.add((x,y))\n",
    "        ans = []\n",
    "        while q:\n",
    "            steps,value,x,y = q.popleft()\n",
    "            if low <= value <= high:\n",
    "                ans.append([steps,value,x,y])\n",
    "            for dx,dy in [(0,-1),(-1,0),(0,1),(1,0)]:\n",
    "                nxtX = x + dx\n",
    "                nxtY = y + dy\n",
    "                if 0 <= nxtX < m and 0<= nxtY < n and (nxtX,nxtY) not in visited and grid[nxtX][nxtY] != 0:\n",
    "                    visited.add((nxtX,nxtY))\n",
    "                    q.append([steps + 1,grid[nxtX][nxtY],nxtX,nxtY])\n",
    "\n",
    "        #print(ans)\n",
    "        return [[r[2],r[3]] for r in sorted(ans)[0:k]]"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def highestRankedKItems(self, grid: List[List[int]], pricing: List[int], start: List[int], k: int) -> List[List[int]]:\n",
    "\n",
    "        res = []\n",
    "        \n",
    "        nodes = deque([start])\n",
    "        \n",
    "        dirs = [\n",
    "            [1, 0],\n",
    "            [-1, 0],\n",
    "            [0, 1],\n",
    "            [0, -1],\n",
    "        ]\n",
    "        visited = set([tuple(start)])\n",
    "        step = 0\n",
    "        if pricing[0] <= grid[start[0]][start[1]] <= pricing[1]:\n",
    "            res.append([0, grid[start[0]][start[1]], start[0], start[1]])\n",
    "\n",
    "        while nodes:\n",
    "            new_nodes = []\n",
    "            step += 1\n",
    "            for row, col in nodes:\n",
    "                for row_diff, col_diff in dirs:\n",
    "                    new_row = row + row_diff\n",
    "                    new_col = col + col_diff\n",
    "                    if 0 <= new_row < len(grid) and 0 <= new_col < len(grid[row]) and grid[new_row][new_col] != 0 and (new_row, new_col) not in visited:\n",
    "                        visited.add((new_row, new_col))\n",
    "                        new_nodes.append([new_row, new_col])\n",
    "                        if pricing[0] <= grid[new_row][new_col] <= pricing[1]:\n",
    "                            res.append([step, grid[new_row][new_col], new_row, new_col])\n",
    "            nodes = new_nodes\n",
    "            if len(res) >= k:\n",
    "                return [[item[2], item[3]] for item in sorted(res)[:k]]\n",
    "        \n",
    "        return [[item[2], item[3]] for item in sorted(res)]\n",
    "        \n",
    "                "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def highestRankedKItems(self, grid: List[List[int]], pricing: List[int], start: List[int], k: int) -> List[List[int]]:\n",
    "        sx, sy = start\n",
    "        lo, hi = pricing\n",
    "        n, m = len(grid), len(grid[0])\n",
    "        seen = set()\n",
    "        seen.add((sx, sy))\n",
    "        q = deque([(sx, sy, 0)])\n",
    "        d = []\n",
    "        if lo <= grid[sx][sy] <= hi:\n",
    "            d.append((sx, sy, 0, grid[sx][sy], sx, sy))\n",
    "        while q:\n",
    "            x, y, step = q.popleft()\n",
    "            for dx, dy in ((-1, 0), (1, 0), (0, -1), (0, 1)):\n",
    "                rx, ry = x + dx, y + dy \n",
    "                if rx < 0 or rx >= n or ry < 0 or ry >= m or grid[rx][ry] == 0 or (rx, ry) in seen: continue\n",
    "                seen.add((rx, ry))\n",
    "                q.append((rx, ry, step + 1))\n",
    "                if lo <= grid[rx][ry] <= hi:\n",
    "                    d.append((rx, ry, step + 1, grid[rx][ry], rx, ry))\n",
    "        # print(d)\n",
    "        d.sort(key=lambda li: (li[2], li[3], li[4], li[5]))\n",
    "        return [[li[0], li[1]] for li in d][:k]"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
